//
// Created by francklinson on 2021/7/19 AT 22:06.
//
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

class Solution {
public:
    /**
     * 层序遍历  从陆地出发
     * @param grid
     * @return
     */
    int maxDistance(vector<vector<int>> &grid) {
        vector<vector<int>> movement{{1,  0},
                                     {-1, 0},
                                     {0,  1},
                                     {0,  -1}};
        queue<pair<int, int>> q;
        int N = (int) grid.size();
        vector<vector<bool>> seen(N, vector<bool>(N, false));
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (grid[i][j] == 1) {
                    // 所有的陆地进入队列
                    q.emplace(i, j);
                    seen[i][j] = true;
                    grid[i][j] = 0;
                }
            }
        }

        int ans = -1;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            auto r = p.first, c = p.second;
            for (int i = 0; i < 4; ++i) {
                int nr = r + movement[i][0];
                int nc = c + movement[i][1];
                if (nr >= 0 and nr < N and nc >= 0 and nc < N and seen[nr][nc] == false) {
                    seen[nr][nc] = true;
                    grid[nr][nc] = grid[r][c] + 1;
                    q.emplace(nr, nc);
                    ans = max(ans, grid[nr][nc]);
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> grid{{1, 0, 1},
                             {0, 0, 0},
                             {0, 0, 0}};
    Solution solution;
    cout << solution.maxDistance(grid) << endl;
    return 0;
}

